import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import javax.management.NotificationFilter;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description: 翻转二叉树
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 * @Date:Create in 15:23  2022/7/21
 */
public class invertTree0226 {

    public static void main(String[] args) {
        String s = "[4,2,7,1,3,6,9]";
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
        root = invertTree1(root);
        TreeNodePrint.printTree(root);
    }

    //递归方法
    public static TreeNode invertTree1(TreeNode root) {
        if(root==null) return root;
        invert(root);
        return root;
    }
    public static void invert(TreeNode root){
        if(root==null) return;
        invert(root.left);
        invert(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    //层序遍历BFS
    public static TreeNode invertTree2(TreeNode root) {
        if(root==null) return null;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len = que.size();
            while(len>0){
                TreeNode node = que.poll();
                swap(node);
                if(node.left!=null) que.offer(node.left);
                if(node.right!=null) que.offer(node.right);
                len--;
            }
        }
        return root;
    }
    public static void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
